package Backtracking


fun main() {
    val sudoku = arrayOf(
            charArrayOf('5', '3', '.', '.', '7', '.', '.', '.', '.'),
            charArrayOf('6', '.', '.', '1', '9', '5', '.', '.', '.'),
            charArrayOf('.', '9', '8', '.', '.', '.', '.', '6', '.'),
            charArrayOf('8', '.', '.', '.', '6', '.', '.', '.', '3'),
            charArrayOf('4', '.', '.', '8', '.', '3', '.', '.', '1'),
            charArrayOf('7', '.', '.', '.', '2', '.', '.', '.', '6'),
            charArrayOf('.', '6', '.', '.', '.', '.', '2', '8', '.'),
            charArrayOf('.', '.', '.', '4', '1', '9', '.', '.', '5'),
            charArrayOf('.', '.', '.', '.', '8', '.', '.', '7', '9')
    )

    solveSudoku(sudoku)
}

fun solveSudoku(board: Array<CharArray>?) {
    if (board == null || board.size == 0)
        return
    solve(board)
}

fun solve(board: Array<CharArray>): Boolean {
    for (i in board.indices) {
        for (j in 0 until board[0].size) {
            if (board[i][j] == '.') {
                var c = '1'
                while (c <= '9') {//trial. Try 1 through 9
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c //Put c for this cell

                        if (solve(board))
                            return true //If it's the solution return true
                        else
                            board[i][j] = '.' //Otherwise go back
                    }
                    c++
                }

                return false
            }
        }
    }
    return true
}

private fun isValid(board: Array<CharArray>, row: Int, col: Int, c: Char): Boolean {
    for (i in 0..8) {
        if (board[i][col] != '.' && board[i][col] == c) return false //check row
        if (board[row][i] != '.' && board[row][i] == c) return false //check column
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
            return false //check 3*3 block
    }
    return true
}